performance

2023-10-11 05:06| 来源: 网络整理| 查看: 265

Nice question. The question indicates that you are considering reuse and portability, these are always good things to keep in mind.

The macros EXIT_SUCCESS and EXIT_FAILURE in stdlib.h. These macros can be used for return values from functions as well as program exit status and might make the code more readable. While there are functions that return 1 or 0 to indicate success or failure, there is no way to identify what the problem was, this will be confusing to users.

Portability

The macro SIZE_MAX is not part of the C99 standard and may not be implemented on all systems, on the systems it is implemented on, it gives the maximum value of an unsigned long, not the maximum addressable memory which seems to be the use in the function ArrayList_ensureCapacity(). This will prevent the program from compiling on some systems and definitely lead to at least a program crash if not a system crash if there is not enough memory on the system.

Asserts

Be careful when using asserts, if the code is not compiled in debug mode, or the optimization switches are used then the assert is optimized out of the function body (NO OP). Use explicit tests for error conditions that can occur at run time. In ArrayList_remove the assert(index < line-size); should be if (index < list-size) {} due to possible user errors. See the definition of assert().

Universality

One of the stated goals is Universality: The data structure is capable to hold any kind of data (I'm currently not sure about the alignment of function pointers).

The current implementation does not implement Universality because it is storing objects rather than pointers to objects. This forces the implementation to use address arithmetic which is error prone. Using void * to point to the objects requires a cast to the proper type by the user, but the library/functions don't need to know the size of the objects and neither does the user of the library.

Using pointers rather than actual objects removes the need for memmove(), memcpy() in the functions ArrayList_append() and ArrayList_remove() as well. This reduces the complexity of ArrayList_remove() to

int ArrayList_remove(ArrayList *list, size_t index) { if (index < list->size) { void **dest = &data[index]; void **src = &data[index + 1]; // Deallocate the void pointer to the object to prevent memory leaks, and invalid references. free(*dest); // Copy the rest of the list to remove the item in data[index]; for (int i = index + 1; i < list->size; i++, dest++, src++ ) { *dest = *src; } list->size--; return 1; } else { return 0; } }

A Typedef Would Make the Code Easier to Implement and Read

First it is questionable if the struct declaration of ArrayList should be in ArrayList.c rather than ArrayList.h. Since the calling code needs to pass in a pointer to the structure it may be better to define the structure in the header file.

There wouldn't need to be as much code as there is if the structure was defined in a typedef in the header file:

typedef struct arraylist { size_t elem_size; // Size of single element to be stored. size_t size; // Number of currently stored elements. size_t capacity; // Number of elements fitting into allocated memory. void **data; // Array of pointers to allocated memory. } ArrayList;

The the function declarations would be:

ArrayList *ArrayList_create(size_t element_size); void ArrayList_destroy(ArrayList *list); size_t ArrayList_getSize(const ArrayList *list); int ArrayList_isEmpty(const ArrayList *list); int ArrayList_trimToSize(ArrayList *list); int ArrayList_append(ArrayList *list, const void *element); int ArrayList_add(ArrayList *list, size_t index, const void *element); int ArrayList_remove(ArrayList *list, size_t index); void *ArrayList_get(const ArrayList *list, size_t index);

No need for struct to be in every fuction declaration or fuction definition.

Performance

Because calloc() zeros the memory that is allocated, the call to calloc may take more time than the call to malloc(), you might want to look at the first answer on this Stack Overflow Question. The same functionallity can be achieved for ArrayList_create() by using a malloc() and then using memset() but the code might be more efficient and clearer if each field was address individually after the struct was created

struct ArrayList *ArrayList_create() { assert(element_size != 0); struct ArrayList *list = malloc(sizeof(struct ArrayList)); if (list) { list->capacity = INITIAL_CAPACITY; list->elem_size = element_size; list->data = (void **) calloc(INITIAL_CAPACITY, sizeof(void *)); if (!list->data) { free(list); list = NULL; } } return list; }

The previous code is somewhat clearer and easier to read than the current implementation.

Another way to improve performance of malloc(), calloc() and realloc() is to malloc() a rather large block of memory() at the beginning of the program and then free it prior to starting the the rest of the program. This action will reserve that large block of memory for the program/process. The functions malloc(), calloc() and realloc() make system calls to get more memory when they've used up the current allocation (sbrk on Unix or Linux). Any time the program makes a system call it is swapped out (context switch) until the system call is completed, on a server or other heavily used computer other programs will run on the CPU during this time and affect performance. On a personal computer this is less of an issue.

The performance will also be enhanced by allocating less space using pointer to void rather than storing actual objects.

【本文地址】

performance

performance

今日新闻

推荐新闻